#include <vector>
#include <algorithm>
using namespace std;


// 三角形的充分且必要条件为三边均为正且满足三角不等式：
// a + b > c、a + c > b、b + c > a；若将三边按非降序排
// 列为 a ≤ b ≤ c，则只需检查 a + b > c 即可；若允许退化三角形（三点共线），不等号改为 ≥。
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int res = 0;

        for (int k = n - 1; k >= 2; k--) { // 固定最大边
            int c = nums[k];
            int l = 0, r = k - 1;

            while (l < r) {
                if (nums[l] + nums[r] > c) {
                    res += (r - l); // [l, r-1] 都能与 r 组成三角形
                    r--;
                } else {
                    l++;
                }
            }
        }
        return res;
    }
};
